In packet-switched networks, two types of data traffic are usually present: unicast and multicast traffic. In unicast traffic a point-to-point connection is established and data is directed from a single source to a single destination, whereas in multicast traffic a point-to-multipoint connection is established and a data packet is directed from a single source to multiple destinations that receive identical copies of the data packet being transmitted. Usually, switch devices support both traffic types, which means that the switching devices must be able to make multiple copies of an incoming multicast packet and transmit the copied packets on output links.
The vast majority of Internet traffic today consists of unicast traffic. However, efficient support for multicast traffic is essential for communication applications such as audio- and video-conferencing, multimedia content distribution, e.g. radio and TV, and remote collaboration, as well as computing applications such as the implementation of collective operations or snoop-based cache coherency in a parallel computer. Ideally, a switching device should be able to achieve high performance under any mix of the two traffic types.
In M. Andrews, S. Khanna, K. Kumaran, “Integrated Scheduling of Unicast and Multicast Traffic in an Input-Queued Switch”, Proc. of IEEE INFOCOM '99, vol. 3, pp. 1144-1151, March 1999, two schedulers are used, namely one for each traffic type. The described scheme consists of scheduling multicast first and using the remaining resources for unicast. This scheme works sequentially. A drawback is that it is not fair, i.e., it does not prevent multicast traffic from starving unicast traffic. A single input loading the switch with multicast packets destined to all the outputs (broadcast) would completely block the flow of unicast packets. The network node cannot guarantee a minimum amount of service to every user and is vulnerable to denial-of-service attacks.
In the state of the art U.S. Pat. No. 6,477,169 Angle et al. a further multicast and unicast scheduling method for a switching device is described. In this embodiment a user has to configure a multicast scheduling frequency that determines how often multicast traffic will be scheduled. If this frequency is set to zero, multicast traffic will not receive any service. If it is larger than zero, multicast traffic will be scheduled at regular intervals. In any given time slot, a decision is made based upon this frequency to schedule multicast traffic or not. If multicast is not to be scheduled in the current time slot, only a unicast scheduling cycle is executed. Otherwise, a unicast and a multicast scheduling cycle are executed in parallel. In this case, the unicast scheduling takes into account the previous multicast results, enlarging the existing multicast schedule with unicast, if possible. In parallel, a new multicast schedule is computed. The key feature of this scheme is that it uses the unicast scheduler and the multicast scheduler in parallel, but every now and then it “prepares” a multicast schedule to be used later, with unicast filling the holes. This means that in this embodiment normally only unicast traffic is scheduled. But at pre-defined timeslots, also multicast schedule is computed. When the multicast schedule is ready, at the next timeslot, the schedule is passed to the unicast scheduler, which tries to enlarge it by performing a scheduling cycle only considering inputs and outputs that are still available. In this scheme conflicts between unicast and multicast are avoided, because the integration is achieved by having unicast add edges to a pre-computed multicast schedule. The unicast scheduler and the multicast scheduler work from time to time in parallel, i.e., they work in form of pipelining, to speed up a serial calculation. The multicast schedule that is calculated is used in a later timeslot, because the unicast scheduler needs information about which outputs are still free. If one tries to use them in the same timeslot, one falls back to a serial scheme; multicast first, and unicast later. In this embodiment the user must manually configure the scheduling frequency. This frequency directly determines the maximum amount of service that multicast can receive. If the actual traffic pattern does not match the expected, programmed value, multicast will not receive enough service and the frequency must be reprogrammed. Traffic conditions are in general extremely hard to predict and may fluctuate strongly, which may require frequent changes in the multicast scheduling frequency; otherwise multicast performance would suffer. Secondly, a latency penalty, depending on the multicast scheduling frequency, is incurred for multicast traffic. This is a result of delaying the issuance of the multicast schedule to the next time slot in which the multicast frequency counter triggers a multicast scheduling cycle. Therefore, if this frequency is low the latency will be very high. In any case, an unnecessary latency is incurred, which is especially undesirable in parallel computing applications. Thirdly, if the multicast scheduling frequency is programmed to a value that does not correspond to the actual value of offered multicast traffic, unfairness may result. In particular, when the frequency is set too low unicast can use an unfair portion of the available bandwidth.